﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

//给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，
//然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
//如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 - 1 。

// 思路；我们可以转化成求数组内⼀段连续的、和为 sum(nums) - x 的最⻓数组。
//class Solution {
//public:
//    int minOperations(vector<int>& nums, int x) {
//        int sum = 0;
//        for (auto e : nums)
//            sum += e;
//        int target = sum - x;
//        if (target < 0)
//            return -1;
//        int len = -1;
//        for (int left = 0, right = 0, total = 0; right < nums.size(); ++right)
//        {
//            // 如果 sum < target ，右移右指针，直⾄变量和⼤于等于 target ，或右指针已经移到头；
//            total += nums[right];
//            //如果 sum > target ，右移左指针，直⾄变量和⼩于等于 target ，或左指针已经移到头；
//            while (total > target)
//            {
//                total -= nums[left++];
//            }
//            // 如果经过前两步的左右移动使得 sum == target ，维护满⾜条件数组的最⼤⻓度，并让下个元素进⼊窗⼝；
//            if (total == target)
//                len = max(len, right - left + 1);
//        }
//
//        if (len == -1)
//            return len;
//        else
//            return nums.size() - len;
//    }
//};


//你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，
//其中 fruits[i] 是第 i 棵树上的水果 种类 。

//你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

//你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
//你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。
// 采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
//一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
//给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。


//a.初始化哈希表 hash 来统计窗⼝内⽔果的种类和数量；
//b.初始化变量：左右指针 left = 0，right = 0，记录结果的变量 ret = 0；
//c.当 right ⼩于数组⼤⼩的时候，⼀直执⾏下列循环：
//i.将当前⽔果放⼊哈希表中；
//ii.判断当前⽔果进来后，哈希表的⼤⼩：
//• 如果超过 2：
//◦ 将左侧元素滑出窗⼝，并且在哈希表中将该元素的频次减⼀；
//◦ 如果这个元素的频次减⼀之后变成了 0，就把该元素从哈希表中删除；
//◦ 重复上述两个过程，直到哈希表中的⼤⼩不超过 2；
//iii.更新结果 ret；
//iv.right++，让下⼀个元素进⼊窗⼝；
//d.循环结束后，ret 存的就是最终结果

//class Solution {
//public:
//    int totalFruit(vector<int>& f) {
//        unordered_map<int, int> hash;
//        int left = 0, right = 0;
//        int ret = -1;
//        while (right < f.size())
//        {
//            hash[f[right]]++;
//            while (hash.size() > 2)
//            {
//                if (--hash[f[left]] == 0)
//                {
//                    hash.erase(f[left]);
//                }
//                left++;
//            }
//            ret = max(ret, right - left + 1);
//            right++;
//        }
//
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    int totalFruit(vector<int>& f) {
//        int hash[100001] = { 0 };
//        int left = 0, right = 0, kind = 0;
//        int ret = -1;
//        while (right < f.size())
//        {
//            if (++hash[f[right]] == 1)
//                kind++;
//            while (kind > 2)
//            {
//                if (--hash[f[left]] == 0)
//                    kind--;
//                left++;
//            }
//
//            ret = max(ret, right - left + 1);
//            right++;
//        }
//
//        return ret;
//    }
//};

//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

//因为字符串 p 的异位词的⻓度⼀定与字符串 p 的⻓度相同，所以我们可以在字符串 s 中构
//造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量；
//◦ 当窗⼝中每种字⺟的数量与字符串 p 中每种字⺟的数量相同时，则说明当前窗⼝为字符串 p
//的异位词；
//◦ 因此可以⽤两个⼤⼩为 26 的数组来模拟哈希表，⼀个来保存 s 中的⼦串每个字符出现的个
//数，另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int hash1[26] = { 0 };
        for (auto e : p)
            hash1[e - 'a']++;
        int hash2[26] = { 0 };
        int len = p.size();
        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];
            if (++hash2[in - 'a'] <= hash1[in - 'a'])
                count++;
            if (right - left + 1 > len)
            {
                char out = s[left++];
                if (hash2[out - 'a']-- <= hash1[out - 'a'])
                    count--;
            }
            if (count == len)
                ret.push_back(left);
        }

        return ret;
    }
};
//int main()
//{
//    return 0;
//}

class CParent
{
public: virtual void Intro()
{
    printf("I'm a Parent, "); Hobby();
}
virtual void Hobby()
{
    printf("I like football!");
}
};
class CChild : public CParent {
public: virtual void Intro()
{
    printf("I'm a Child, "); Hobby();
}
virtual void Hobby()
{
    printf("I like basketball!\n");
}
};

int main(void)
{
    CChild* pChild = new CChild();
    CParent* pParent = (CParent*)pChild;
    pParent->Intro();
    return(0);
}